Merkle Search Tree
論文
概要
普通の2分木のMerkle Treeでは、木がうまくバランスするようにする再構築の過程で順序が破壊されるので、うまくいかない MSTのデータ構造
https://scrapbox.io/files/656996c7786dd100247ba746.png
特徴
アイテムの集合は、決定論的に一意な木の表現を持つ
キーの順序は保持される
ツリーは常にバランスが取れている(確率的) ←どういうこと?kekeho.icon
Merkle Search Treeの構成
MSTは、全順序の空間$ \mathbb{K}に含まれる要素$ eの順序付き集合を作る
要素は、$ \mathbb{V}(値)に紐付けられたタグとなる。$ \mathbb{K}はキーの集合
$ \mathbb{V}はデフォルト要素の$ \perpを持つ。$ f: \mathbb{K} \rightarrow \mathbb{V}にキーが存在しないことを示すために用いられる。
予め、$ e \in \mathbb{K}の順序が決定的に決まっているからできる。例えば、挿入時に順序付けをするような場合では一筋縄ではいかないんだろうkekeho.icon
Leafがレイヤ0
レイヤ$ lにいるノードたちは、連続するアイテムのブロックであり、その境界は$ l' \gt lのアイテムに対応する
MSTに格納される値は、そのハッシュを計算し、その値をベースレイヤに書き込む
書き込むレイヤ$ l(x)は、$ h_B(x)のゼロのみで構成される最長の接頭辞の長さで決定される
$ h_B: Digestの空間サイズが$ 2^Bとなるようなハッシュ関数
SHA512ならBが512ということなんだと思うkekeho.icon
ポインタとして下レイヤのハッシュを書く
先頭ビットの0の数でレイヤを測る
各ノードのサイズは一定のサイズを持たない(普通のB-Treeはページサイズとかがあったはず?kekeho.icon)
操作の定義
$ \mathrm{get}(f, k): ツリー$ fからキー$ kに対応する値を読み取る
$ \mathrm{getrange}(f, \lbrack k_0, k_1 \rbrack ): ツリー$ fからキー範囲が$ k_0 ~ $ k_1に含まれる値の集合を読み取る
$ \mathrm{put}(f, k, v): ツリー$ fのキー$ kに値$ vを書き込む
$ \mathrm{delete}(f, k): ツリー$ fからキー$ kを消す
非リーフ層で値の追加・削除が発生すると、Split・Mergeが発生する可能性がある。
バランスと深さ
あるアイテムがレイヤ$ lにある確率は$ p_l = (\frac{1}{B})^{l} \frac{B-1}{B}
レイヤ$ lのアイテム数は、レイヤ$ l' > lの境界でSplitされるので、レイヤ$ lのノードは平均$ B-1個の値が格納され、リーフでない層は$ B個のノードを持つ
データセット比較の効率性
Merkle Search Trees as CRDT $ \mathbb{V}がCRDTであり、マージ操作$ \sqcup_{\mathbb{V}}( $ \forall x, \perp\sqcup _\mathbb{V}x=x\sqcup_\mathbb{V}\perp=x)を持つ
具体的にマージ操作をどう定義すればいいんだ? kekeho.icon
さすれば、$ \sqcup\mathrm{v}:(f\sqcup g)(x)=f(x)\sqcup \mathrm{v}g(x)で定義されるMST$ f,g: \mathbb{K} \rightarrow \mathbb{V}はCRDTとなる
例: $ \mathbb{K}のG-set
$ \mathbb{V} = \{\perp,\ \mathsf{T}\}とすれば、OK
たしかにねーkekeho.icon
アルゴリズム
https://scrapbox.io/files/656c40161aff3200231fe81e.png
アプリケーション: 分散イベントストア
$ \mathbb{V} = {T, F}
$ \mathbb{K}: イベント空間(論理クロック or 実時間の近似値で並べられる)